package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/8 10:55
 */
public class 射箭比赛的最大得分重置版 {

    /*
     这是 arignote 的写法
     ，我就猜测 他会写的 很吊！

      下面的时间复杂度 是  ： O （ 2 ^ 12 * 12 ）
      因为 在 最后 每次最后，还会进行一个 数组的拷贝，
      递归时间复杂的计算： 递归的深度 * 递归的分支数 * 最后的结果处理数（比如涉及到一些数组的copy ，或者字符串的 比较之类的）
     */
    private int max, result[];

    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        maximumBobPoints(1, 0, new int[12], numArrows, aliceArrows);
        return result;
    }

    private void maximumBobPoints(int i, int points, int[] curr, int numArrows, int[] aliceArrows) {
        if (numArrows >= 0) {
            if (i < 12) {
                maximumBobPoints(i + 1, points, curr, numArrows, aliceArrows);
                maximumBobPoints(i + 1, points + i, curr, numArrows - (curr[i] = aliceArrows[i] + 1), aliceArrows);
                curr[i] = 0;
            } else if (points >= max) {
                max = points;
                curr[0] = numArrows;
                result = curr.clone();
            }
        }
    }


    /*
     直接 递归回溯的做法！
     把 arignote 的写法转换成自己的思想！
     */


    int ans[] , mx = 0;

    /*
     *
     * @param index
     * @param nums
     * @param rest
     * @param curr 中间的 递归 数组 ， 体会一下这个数组的作用！
     * @param points 记录递归的每个分支路径结果的 得分， 然后统计全局最大值 mx
     */
    public void recursion(int index,int nums[],int rest,int[] curr,int points){
        if(rest == 0 || index == nums.length){
            if(points > mx){
                mx = points;
                ans = curr.clone();
                ans[0] = rest; // 走到最后，把剩余的箭 放到 0 位置上面！
            }
            return ;
        }
        // no
        recursion(index + 1,nums,rest,curr,points);
        // 选择 射箭 ,前提是 能射箭
        if(rest - nums[index] >= 1){
            curr[index] = nums[index] + 1;
            recursion(index + 1,nums, rest - curr[index],curr,points + index);
            // 递归回来之后，要进行回溯， 好进行其他路径的一个 选择
            curr[index] = 0;
        }
    }




    /*
     dp 的做法
     */
    public int recursion(int index,int rest,int nums[]){
        if(index == nums.length || rest == 0){
            return 0;
        }
        int ans = 0;
        // no
        ans = recursion(index + 1,rest,nums);
        // if  can choose
        if(rest - nums[index] >= 1){
            ans = Math.max(ans,recursion(index + 1,rest - nums[index]  - 1,nums) + index);
        }

        return ans;
    }


    public int[] solution(int arrows,int aliceArrows[]){
        int ans [] = new int[aliceArrows.length];
        int dp[][] = new int[aliceArrows.length + 1][arrows + 1];
        int path[][] = new int[aliceArrows.length + 1][arrows + 1]; // path[index][rest] = 0 表示 从决策 ①过来的， = 1 表示从决策 ② 过来的

        for(int index = aliceArrows.length - 1;index >= 0;index--){
            for(int rest = 0;rest <= arrows; rest ++){
                dp[index][rest] = dp[index + 1][rest]; // 决策①
                if(rest - aliceArrows[index] >= 1){ // 决策②
                    if(dp[index + 1][rest] <= dp[index + 1][rest - aliceArrows[index] - 1] + index ){ // 如果决策 ① 和② 结果相同， 那么也走 决策②（当然也可以走决策①）
                        dp[index][rest] = dp[index + 1][rest - aliceArrows[index] - 1] + index;
                        path[index][rest] = 1; //标记路径
                    }
                }
            }
        }

        int count = arrows;
        // 不用 path 数组的做法， 本质上，还是 变相的使用 了path 数组
        for(int index = 1;index < aliceArrows.length;index++){
            if(dp[index][arrows] > dp[index + 1][arrows]){ // 表示 不是 从决策 ① 过来的 而是从决策②过来的， 如果是决策①当前靶子是跳过的，不射箭
                ans[index] = aliceArrows[index] + 1;
                arrows -= ans[index];
            } // 从决策 ①过来的不用填， 数组初始化， 本身就是0
        }
        ans[0] = arrows; // 规定 最后 把 剩余的 arrows 放在 0 号靶子上面



        // 使用path 数组  显然 path 数组 这种 会更加的 通用一些！
        for(int index = 1;index < aliceArrows.length;index++){
            if(path[index][count] == 1){
                count -= ans[index] = aliceArrows[index] + 1;
            }
        }
        ans[0] = count;
        return ans;
    }



    @Test
    public void test(){
        int nums[] = {1,2,3,4,5};
        int ans[] = nums.clone();
        System.out.println(Arrays.toString(ans));
        System.out.println(ans == nums);
    }


    public void f(){

        int maxScore = 100;
        int nums[][] = new int[10][10];
        int arrows = 10;

        for(int i = 0;i < nums.length;i++){
            if(nums[i][arrows] != nums[i + 1][arrows]){

            }
        }
    }



}
